package golang

import "gitee.com/allowall-package/goutil/fn"

func QuickSort(a []int, s, e int) {
	if s >= e {
		return
	}

	// 设置基数
	m := a[(s+e)/2]
	i, j := s, e

	for {
		// 从前往后获取超过m的索引
		for a[i] < m {
			i++
		}

		// 从后往前获取小于m的索引
		for a[j] > m {
			j--
		}

		// fn.Dump(i, j)
		// 互换两个值，大于m的放后面，小于m的放前面
		if i <= j {
			a[i], a[j] = a[j], a[i]

			// 换完之后，起始位置分别向中间移一位，进入下次查找
			i++
			j--

			// 没有需要换的元素，结束循环
		} else {
			break
		}
	}

	// 前边部分进行快排
	if s < j {
		QuickSort(a, s, j+1)
	}

	// 后边部分进行快排
	if e > i {
		QuickSort(a, i-1, e)
	}

}

func QuickSortTest() {
	fn.SliceRand(a)
	s := make([]int, len(a))
	copy(s, a)

	QuickSort(a, 0, len(a)-1)
	fn.Dump(fn.FuncInfo(), s, a)
}
